package com.lyz.dataStructure.sort;

import java.util.Arrays;
        import java.util.Random;

/**
 *@Author:759057893@qq.com Lyz
 *@Date: 2019/4/2 15:51
 *@Description:
 **/

/*
希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        Random ran = new Random();
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++) {
            arr[i] = ran.nextInt(100) + 1;
        }
        System.out.println(Arrays.toString(arr));
        shell_sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void shell_sort(int[] arr) {
        int gap = 1, i, j, len = arr.length;
        int temp;
        while (gap < len / 3)
            gap = gap * 3 + 1;      // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
        for (; gap > 0; gap /= 3) {
            for (i = gap; i < len; i++) {
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                    arr[j + gap] = arr[j];
                arr[j + gap] = temp;
            }
        }
    }
}
